#!/usr/bin/perl

#Copyright (c) 2005-2006 Apple Computer, Inc.  All Rights Reserved.
#
#This program is free software; you can redistribute it and/or modify
#it under the terms of the GNU General Public License as published by
#the Free Software Foundation; either version 2 of the License, or
#(at your option) any later version.
#
#This program is distributed in the hope that it will be useful,
#but WITHOUT ANY WARRANTY; without even the implied warranty of
#MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#GNU General Public License for more details.
#
#You should have received a copy of the GNU General Public License
#along with this program; if not, write to the Free Software
#Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

=pod

=head1 SYNOPSIS

buildfink -- Build every package in Fink

=head1 USAGE

    buildfink [-n] [--infofilter SCRIPT] [--patchdir DIR] [--skip PACKAGE] [--skip PACKAGE] [--find-orphan-files] [--validate] [--build-as-nobody] [--max-log-size [P:]N] [--max-build-time [P:]T] [--packages PKGLIST] [--rebuild-deps] [--dirty] [FINKDIR OUTDIR]
    buildfink [-r CHECKPOINT]

C<buildfink> builds every package in Fink, taking care of things like avoiding repeated building
of packages and maintaining a log for every package build.  It collects all of the logs, package
files, and built packages under a single output directory tree.

C<FINKDIR> specifies the root of your Fink installation; this is usually C</sw>.

C<OUTDIR> specifies the path to the output directory; this directory must not already exist.

If C<-n> is given, the script will do nothing but emit an ordered list of packages that it would
build and exit.

The C<--infofilter> option, if specified, allows the package .info and .patch files to be filtered
prior to building packages.  The specified script will be invoked with the basename of the info
or patch file as an argument and will receive the contents of the file on standard output; it should
emit the modified file on standard output.

The C<--patchdir> option, if specified, allows you to have an extra directory of .info and
.patch files which will be inserted into the package tree.  Any files
obtained via this mechanism are not subject to filtering via C<--infofilter>.

The C<--skip> option, which may be specified multiple times, allows the given package to be skipped.
Skipped packages will not be built, nor will any packages which depend on them.

The C<--validate> option, if specified, causes buildfink to validate packages
as it builds them.

The C<--tests> option runs any test suites specified in an InfoTest section (not yet implemented).

The C<--find-orphan-files> option, if specified, will detect files installed
into the prefix which aren't actually part of the binary package.

The C<--build-as-nobody> option, if present, causes buildfink to build
packages as "nobody" instead of root; if C<--build-as-nobody=try> is specified,
it will try building as root if that fails and keep track of which packages
only succeed when built as root.

buildfink places limits on the maximum size of the log file for an individual
build and the build time of an individual package to prevent runaway packages
from breaking the build.  C<--max-log-size N> and C<--max-build-time T> can be
used to adjust these limits.  An C<N> or C<T> of 0 will disable the
corresponding limit.  C<N> is in bytes, unless it has a suffix of C<K>, C<M>,
or C<G> indicating kilobytes, megabytes, and gigabytes respectively.
C<T> is in seconds, unless it has a suffix of C<m> or C<h> indicating,
respectively, minutes and hours.  The defaults are 250 megabytes and 4 hours
respectively.  Package-specific limits can be provided by specifying
C<packagename:> in front of the limit value.  For instance,
C<--max-build-time openoffice.org:24h> would specify a 24-hour limit for 
openoffice.org.

Normally, buildfink will attempt to build every package it knows about.  To
build only a subset of packages, give C<--packages PKGLIST>, where C<PKGLIST>
is a comma-separated list of packages or C<--package-file PKGFILE>, where
C<PKGFILE> is a list containing one package name per line (blank lines and
comments starting with # are also allowed.)  To specify packages that you don't
want to rebuild unless they aren't up to date, use the C<--packages-no-rebuild>
(or C<--package-file-no-rebuild>) options.  Dependencies of things you specify
via C<--packages> are automatically added with that behaviour.

If only building a fixed list of packages,
you may also want the C<--dirty> option to avoid purging all
non-essential packages before performing each build.  The
C<--rebuild-deps> option will add any packages which depend on anything
in C<PKGLIST> .  C<--no-copy-info> makes symlinks to the .info files from the
Fink trees into the output directory (instead of copying the files over);
the copy behaviour is useful if you want to maintain an archive of the package
versions in your build, but if you don't need that you can save the space
and time.

=head3 File Database

If you'd like to have C<buildfink> create a database of the files in each Fink
package it builds (which can be viewed with the C<fdb> web interface and
utilities which come with C<buildfink>), specify a value for the C<--fdb-store>
option.  The value tells C<buildfink> where to store those data; the only valid
value at the moment is C<DBI>.  Other C<fdb> options are C<--fdb-dbtype>
(valid values: any DBD module name), C<--fdb-db> (the name of the database
to use), C<--fdb-dbuser>, and C<--fdb-dbpass>.

=head2 CHECKPOINTS

Sometimes there will be system issues partway through a build.  For instance, a
recalcitrant package can get stuck in a log-spewing loop, which will result in
a build log which fills up the disk.  Or maybe there will be a power outage.
Thus, buildfink dumps its state to disk after every package build in the file
C<checkpoint> inside the build directory.  The C<-r> option can be
used to resume a run from a checkpoint file.

=cut

use strict;
use warnings;
use File::Basename;
use File::Copy;
use File::Find;
use Data::Dumper;
use POSIX qw(sys_wait_h dup2 setsid);
use Getopt::Long;
use FindBin qw($Bin);
use lib "$Bin/lib";
use FinkLib;
use FinkFDB;

our($Bin, $FinkBuildFlags, $FinkConfig, $FinkDir, $RunDir, $DryRun, $infofilter, $patchdir, @skiplist, $checkpoint, $CheckFiles, $DoValidate, $BuildNobody, $Dirty, $RebuildDeps, $BuildAll, $NoCopyInfo, $FDB);
our $VERSION = 1.00;

our $max_build_time = 60*60*4;
our $max_log_size = 1024*1024*250;
our %max_build_time_forpkg = ();
our %max_log_size_forpkg = ();

END { $FDB->finish() if $FDB; }

sub limit_arg {
  my($arg, $val) = @_;
  my $pkg;

  $pkg = $1 if $val =~ s/^(.*)://;

  if ($val =~ s/([kmgh])b?$//i) {
    my $suffix = $1;
    if ($suffix eq "k") {
      $val *= 1024;
    } elsif ($suffix eq "m") {
      if ($arg =~ /time/) {
	$val *= 60;
      } else {
	$val *= 1024*1024;
      }
    } elsif ($suffix eq "h") {
      $val *= 60*60;
    } elsif ($suffix eq "g") {
      $val *= 1024*1024*1024;
    }
  }

  if ($arg =~ /time/) {
    if ($pkg) {
      $max_build_time_forpkg{$pkg} = $val;
    } else {
      $max_build_time = $val;
    }
  } else {
    if ($pkg) {
      $max_log_size_forpkg{$pkg} = $val;
    } else {
      $max_log_size = $val;
    }
  }
}

# Keys will be package names.  Values will be:
my %pkglist;
use constant PKGSTATUS_INSTALLED => 3;
use constant PKGSTATUS_REBUILD => 2;
use constant PKGSTATUS_INSTALL => 1;
use constant PKGSTATUS_PROCESSING => 0;
use constant PKGSTATUS_FAILED => -1;
use constant PKGSTATUS_SKIP => -2;

$BuildAll = 1;
$FinkBuildFlags = "";

sub packageList {
  my($pkglist, $arg, $val) = @_;
  my $status = PKGSTATUS_REBUILD;

  $status = PKGSTATUS_INSTALL if $arg =~ s/-no-rebuild//;
  $BuildAll = 0;

  if ($arg eq "packages") {
    $pkglist->{$_} = $status foreach split(/,/, $val);
  } else {
    open(INPUT, $val) or die "Couldn't open packages file $val: $!\n";
    while (<INPUT>) {
      chomp;
      s/#.*//;
      s/^\s+ //; s/\s+ $//;
      next if /^$/;
      $pkglist->{$_} = $status;
    }
    close INPUT;
  }
}

my %fdbopts = (dbuser => "", dbpass => "", db => "", dbtype => "");
my $opts_ok = GetOptions(
			 "n" => \$DryRun,
			 "infofilter=s" => \$infofilter,
			 "patchdir=s" => \$patchdir,
			 "skip=s" => \@skiplist,
			 "r=s" => \$checkpoint,
			 "validate" => \$DoValidate,
			 "find-orphan-files" => \$CheckFiles,
			 "dirty" => \$Dirty,
			 "rebuild-deps" => \$RebuildDeps,
			 "packages=s" => sub {packageList(\%pkglist, @_)},
			 "package-file=s" => sub {packageList(\%pkglist, @_)},
			 "packages-no-rebuild=s" => sub {packageList(\%pkglist, @_)},
			 "package-file-no-rebuild=s" => sub {packageList(\%pkglist, @_)},
			 "no-copy-info" => \$NoCopyInfo,
			 "build-as-nobody:s" => \$BuildNobody,
			 "max-build-time=s" => \&limit_arg,
			 "max-log-size=s" => \&limit_arg,
			 "fdb-store=s" => \$fdbopts{store},
			 "fdb-dbtype=s" => \$fdbopts{dbtype},
			 "fdb-db=s" => \$fdbopts{db},
			 "fdb-dbuser=s" => \$fdbopts{dbuser},
			 "fdb-dbpass=s" => \$fdbopts{dbpass},
			);
if (@ARGV != 2 and not (($DryRun and @ARGV == 1) or $checkpoint)) {
  warn "You must specify a Fink directory and an output directory.\n";
  $opts_ok = 0;
} else {
  ($FinkDir, $RunDir) = @ARGV;
  $FinkDir =~ s!/$!!;
}
if ($checkpoint and not -f $checkpoint) {
  warn "The specified checkpoint file does not exist.\n";
  $opts_ok = 0;
} elsif ($checkpoint and ($DryRun or $infofilter or $patchdir or @skiplist or @ARGV)) {
  warn "You may not specify any other options when restoring from a checkpoint.\n";
  $opts_ok = 0;
}
if ($FinkDir and not -d $FinkDir) {
  warn "The specified Fink directory does not exist.\n";
  $opts_ok = 0;
} elsif ($FinkDir and not -x "$FinkDir/bin/fink") {
  warn "The specified Fink directory does not appear to contain a Fink installation.\n";
  $opts_ok = 0;
}
if (!$DryRun and $RunDir and -d $RunDir) {
  warn "The specified output directory already exists.\n";
  $opts_ok = 0;
}
if ($infofilter and not -x $infofilter) {
  warn "The specified info filter cannot be executed.\n";
  $opts_ok = 0;
}
if ($patchdir and not -d $patchdir) {
  warn "The specified patch directory does not exist or is not a directory.\n";
  $opts_ok = 0;
}
if ($BuildNobody and $BuildNobody ne "try") {
  warn "The only valid value for '--build-as-nobody' is 'try'.\n";
  $opts_ok = 0;
}
if ($fdbopts{store}) {
  $FDB = FinkFDB->new(%fdbopts);
  $FDB->initialize();
}

if (!$opts_ok) {
  die "See 'perldoc $0' for more information.\n";
}

if ($checkpoint) {
  restoreCheckpoint($checkpoint);
  exit();
}

restoreSystem();
prepSystem();
FinkLib::purgeNonEssential() unless $Dirty;
FinkLib::readPackages();
FinkLib::removeBuildLocks();

if ($BuildAll) {
  %pkglist = map { $_ => PKGSTATUS_REBUILD } FinkLib::filterSplitoffs(Fink::Package->list_packages()) if $BuildAll;
} else {
  # filterSplitoffs isn't available until we've initialized Fink.
  # We can't initialize Fink until after option processing is done.
  # So, --packages doesn't filter splitoffs, and we do it here...
  %pkglist = map { $_ => PKGSTATUS_REBUILD } FinkLib::filterSplitoffs(keys %pkglist);
}

foreach (FinkLib::filterSplitoffs(@skiplist)) {
  $pkglist{$_} = PKGSTATUS_SKIP;
  logPackageFail($_, "Package is on the skip list");
}

# Don't try to install uninstalled virtual packages.
# We can't use them to satisfy dependencies and we can't build them...
my $vpinfo = Fink::VirtPackage->list();
while (my($pkgname, $hash) = each(%$vpinfo)) {
  if ($hash->{status} !~ / installed$/) {
    $pkglist{$pkgname} = PKGSTATUS_SKIP;
    logPackageFail($pkgname, "Package is an uninstalled virtual package.");
  } else {
    $pkglist{$pkgname} = PKGSTATUS_INSTALLED;
  }
}


if (!$BuildAll and $RebuildDeps) {
  # Build up a map showing what each package is depended on by
  my %dependents;
  foreach my $pkg (FinkLib::filterSplitoffs(Fink::Package->list_packages())) {
    my $obj = FinkLib::objForPackageNamed($pkg);
    next unless $obj and !$obj->is_type('dummy');
    my @deps;
    eval {
      @deps = $obj->resolve_depends(1, "depends");
    };
    if ($@) {
      doLog("Couldn't get dependencies for $pkg: $@");
      next;
    }
    foreach my $dep (@deps) {
      foreach my $alt (map {$_->get_name()} @$dep) {
	$dependents{$alt} ||= {};
	$dependents{$alt}->{$pkg} = 1;
      }
    }
  }

  foreach my $pkg (grep { $pkglist{$_} == PKGSTATUS_REBUILD } keys %pkglist) {
    my @deps = FinkLib::filterSplitoffs(FinkLib::getDependentsRecursive($pkg, \%dependents));
    doLog("Recursive inverse deps: " . join(", ", @deps));
    foreach my $dep (@deps) {
      $pkglist{$dep} = PKGSTATUS_REBUILD;
    }
  }
}

if (!$DryRun) {
  # Then copy the .info files to our private repository and patch them if necessary.
  patchPackages(keys %pkglist);

  # Only let Fink see our modified packages
  injectPackages() if $BuildAll;
}

# Now do the run
initCheckpoint(\%pkglist) unless $DryRun;
FinkLib::installEssentials() unless $DryRun;
buildAll(\%pkglist);
doLog("Done building");
restoreSystem();

### ==== buildfink framework functions ====

# Prepare the system
sub prepSystem {
  $FinkConfig = FinkLib::initFink($FinkDir);
  return if $DryRun;

  # Test whether fink supports --tests/--validate
  if ($DoValidate) {
    open(FINK, "-|", "fink -V --validate on 2>&1") or die "Couldn't launch fink: $!\n";
    my $supportsValidation = 1;
    while (<FINK>) {
      if (/unknown option/i) {
	$supportsValidation = 0;
	last;
      }
    }
    close(FINK);

    if ($supportsValidation) {
      $FinkBuildFlags = " --validate=warn ";
    } else {
      $FinkBuildFlags = " -m ";
    }
  }


  mkdir($RunDir);
  mkdir("$RunDir/$_") for qw(pkginfo logs src out validate nobody);
  mkdir("$RunDir/pkginfo/finkinfo");
  mkdir("$RunDir/pkginfo/binary-darwin-x86_64");

  open(LOG, ">>", "$RunDir/log.txt") or die "Couldn't open log: $!\n";

  # Make STDOUT and STDERR go to the log.
  close(STDOUT);
  close(STDERR);
  open(STDOUT, ">&", \*LOG);
  open(STDERR, ">&", \*LOG);
  select STDERR; $| = 1;
  select STDOUT; $| = 1;

  doLog('buildfink $Revision$');
  doLog("Skipping packages: " . join(" ", @skiplist));
  doLog("BuildVersion: " . `sw_vers -buildVersion 2>&1`);
  doLog(`gcc -v 2>&1 | tail -1`);
  doLog(`ld -v 2>&1`);
}

sub restoreSystem {
  unlink("$FinkDir/fink/dists/buildfink");
}

sub doLog {
  my($fmt, @args) = @_;

  print scalar(localtime()) . ": ";
  my($out) = sprintf($fmt, @args);
  chomp($out);
  print "$out\n";
}

sub doValidateWarn {
  my($pkg, $fmt, @args) = @_;

  open(VAL, ">>", "$RunDir/validate/$pkg") or die "Couldn't open validation log for $pkg: $!\n";
  my($out) = sprintf($fmt, @args);
  chomp($out);
  print VAL "$out\n";
  close VAL;
}

# Log a package-specific failure
sub logPackageFail {
  my($pkg, $reason) = @_;
  open(LOG, ">$RunDir/logs/$pkg.log");
  print LOG "Failed: $reason.\n";
  close LOG;
}

# Allow Fink to see our modified packages and only those packages
sub injectPackages {
  symlink("$RunDir/pkginfo", "$FinkDir/fink/dists/buildfink");
  $FinkConfig->set_param("Trees" => "buildfink");
  FinkLib::readPackages();
}

# Copy all package files to the buildfink repository and, if necessary,  patch the .info/.patch files.
sub patchPackages {
  my(@pkgnames) = @_;

  doLog("Patching packages.");

  foreach my $pkgname (@pkgnames) {
    next unless $pkgname;
    next if grep { $_ eq $pkgname } @skiplist;

    my $pkg = FinkLib::objForPackageNamed($pkgname);
    next unless $pkg and !$pkg->is_type('dummy');
    my $info = $pkg->get_info_filename();
    if (!$info) {
      die "Couldn't get info for $pkgname: " . Data::Dumper::Dumper($pkg) . "\n";
    }

    my $dir = dirname($info);

    # There are a couple of packages where the package name is foo-bar
    # but the patch is named foo (namely, emacs21-nox).  We want to get any
    # .patch files along with their corresponding .info files.
    my $pkg2 = $pkgname;
    $pkg2 =~ s/(.*)-.*/$1/;

    opendir(INFODIR, $dir) or die "Couldn't open info directory $dir: $!\n";
    while (my $file = readdir(INFODIR)) {
      next if $file eq "." or $file eq ".." or $file eq "CVS";

      # We have a libpqpp-4.0.patch but not libpqpp-4.0 package.
      # Handle this as a special case...
      next unless
	$file =~ /^\Q$pkgname\E/ or
	  $file =~ /^\Q$pkg2\E/ or
	    $file eq "libpqpp-4.0.patch";

      my $newfile = $file;

      if ($file eq "libpqpp-4.0.patch") {
	$newfile = $file;
      }

      if ($file =~ /\.(info|patch)$/) {
	patchFile("$dir/$file", "$RunDir/pkginfo/finkinfo/$newfile");
      } else {
	my $cpfn = $NoCopyInfo ? \&symlink : \&copy;
	$cpfn->("$dir/$file", "$RunDir/pkginfo/finkinfo/$newfile") or die "Couldn't copy/link $dir/$file: $!\n";
      }
    }
    closedir(INFODIR);
  }

  if ($patchdir) {
    opendir(PATCHDIR, $patchdir) or die "Couldn't open $patchdir: $!\n";
    my @extrapatches = grep {$_ ne "." and $_ ne ".."} readdir(PATCHDIR);
    closedir(PATCHDIR);
    foreach my $patch (@extrapatches) {
      my $cpfn = $NoCopyInfo ? \&symlink : \&copy;
      $cpfn->("$patchdir/$patch", "$RunDir/pkginfo/finkinfo/$patch") or die "Couldn't copy/link $patchdir/$patch: $!\n";
    }
  }
}

# Patch a particular file with our specific modifications
sub patchFile {
  my($oldfile, $newfile) = @_;

  die "Copying file $oldfile to self!\n" if $oldfile eq $newfile;

  open(IN, "<", $oldfile) or die "Couldn't open $oldfile for reading: $!\n";
  local $/ = undef;
  my $in = <IN>;
  close IN;

  open(OUT, ">", $newfile) or die "Couldn't open $newfile for writing: $!\n";
  if ($infofilter) {
    my $pid = open(FILTER, "|-");
    if (!defined($pid)) {
      die "Couldn't fork: $!\n";
    } elsif (!$pid) {
      close(STDOUT);
      dup2(fileno(OUT), 1);
      exec($infofilter, basename($newfile)) or die "Couldn't exec $infofilter: $!\n";
    } else {
      close OUT;
      print FILTER $in;
      close FILTER;
      wait();
    }
  } else {
    print OUT $in;
    close OUT;
  }
}

# Do the build command, logging to the package log and enforcing time and
# space limits.
sub doBuild {
  my($buildcmd, $pkg) = @_;
  my $logsize = 0;

  # Don't do the naive thing with || because we want to be able to
  # disable limits for specific packages by specifying a limit of 0.
  my $max_size = exists($max_log_size_forpkg{$pkg}) ? $max_log_size_forpkg{$pkg} : $max_log_size;
  my $max_time = exists($max_build_time_forpkg{$pkg}) ? $max_build_time_forpkg{$pkg} : $max_build_time;

  local $SIG{PIPE} = 'IGNORE';
  my $pid = open(BUILD, "-|");
  if (!defined($pid)) {
    doLog("Couldn't fork: $!\n");
    die "Couldn't fork: $!\n";
  } elsif ($pid == 0) {
    $| = 1;

    # We want to be able to kill this process and all its children.
    # Making them be in their own process groups accomplishes this.
    # TODO: Salt the earth so that nothing can grow in its place.
    setsid();

    exec($buildcmd) or die "Couldn't exec: $!\n";
  }

  open(BUILDLOG, ">", "$RunDir/logs/$pkg.log") or do {
    doLog("Couldn't open $RunDir/logs/$pkg.log: $!");
    die "Couldn't open $RunDir/logs/$pkg.log: $!\n";
  };
  print BUILDLOG "$buildcmd\n";

  my($rin, $win, $ein) = ('', '', '');
  vec($rin, fileno(BUILD), 1) = 1;
  $ein = $rin;
  my($rout, $wout, $eout);
  my $buff;

  eval {
    local $SIG{ALRM} = sub { die "alarm\n"; };
    alarm($max_time) if $max_time;

    while (select($rout = $rin, $wout = $win, $eout = $ein, $max_time ? ($max_time + 5) : undef)) {
      my $nbytes = sysread(BUILD, $buff, 4096);
      $logsize += $nbytes;
      last unless $nbytes;
      print BUILDLOG $buff;

      if ($max_size and $logsize > $max_size) {
	alarm(0);
	print BUILDLOG "\nFailed: Log size limit exceeded.\n";
	# Negative signals send to process group
	kill(-15, $pid);
	sleep(10) if kill(0, $pid);
	kill(-9, $pid);
	FinkLib::readPackages();
	FinkLib::removeBuildLocks();
	last;
      }
    }
  };
  alarm(0);
  if ($@) {
    die unless $@ eq "alarm\n";
    print BUILDLOG "\nFailed: Build process timed out.\n";
    kill(-15, $pid);
    sleep(10);
    kill(-9, $pid);
    FinkLib::readPackages();
    FinkLib::removeBuildLocks();
  }

  close(BUILDLOG);
  close(BUILD);
  if (WIFEXITED($?)) {
    return WEXITSTATUS($?);
  } else {
    return -1;
  }
}

sub getDebFiles {
  return unless $FDB;
  my($obj) = @_;

  my $pkg = $obj->get_name();
  my $deb = $obj->get_debfile();

  doLog("Getting files for $pkg\n");

  my @files;
  open(DPKGDEB, "-|", "dpkg-deb", "-c", $deb) or die "Couldn't run dpkg-deb: $!\n";
  while (<DPKGDEB>) {
    chomp;
    my($flags, $owners, $size, $date, $time, $path) =
      split(/\s+/, $_, 6);
    $path =~ s/ link to.*//;
    $path =~ s/ -> .*//;
    $path =~ s!^\.!!;

    next if $FinkDir =~ m!^\Q$path\E!;
    $path =~ s!^\Q$FinkDir\E!%p!;

    my($user, $group) = split(m!/!, $owners);
    push @files, {
		  flags => $flags,
		  path => $path,
		  size => $size,
		  user => $user,
		  group => $group,
		 };
  }
  if (!close(DPKGDEB)) {
    die "dpkg-deb -c $deb failed; corrupt .deb?\n";
  }

  $FDB->addPackageFiles($pkg, \@files);
}
sub setPackageStatus {
  my($pkglist, $pkg, $status) = @_;
  $pkglist->{$pkg} = $status;
  updateCheckpoint($pkg => $status);
}

sub setPackageFail {
  my($pkglist, $pkg, $reason) = @_;
  logPackageFail($pkg, $reason);
  setPackageStatus($pkglist, $pkg, PKGSTATUS_FAILED);
}

# Try to build an individual package.
sub recurseOnDepends {
  my($pkglist, $pkg, $install, $finkfiles) = @_;
  my $orig_status = $pkglist->{$pkg};
  $pkglist->{$pkg} = PKGSTATUS_PROCESSING;
  doLog("Trying to satisfy $pkg");

  my $obj = FinkLib::objForPackageNamed($pkg);
  if (!$obj) {
    setPackageFail($pkglist, $pkg, "Couldn't get package object: $FinkLib::ERR");
    return;
  }

  if ($obj->is_type('dummy')) {
    doLog("$pkg is a dummy.");
    setPackageStatus($pkglist, $pkg, PKGSTATUS_INSTALLED);
    return 1;
  }

  # Build deps, and maybe run deps
  my(@bdeps, @rdeps);
  eval {
    @bdeps = $obj->resolve_depends(2, "depends");
    @rdeps = $obj->resolve_depends(0, "depends") if $install;
  };
  if ($@ and $@ =~ /[a-z]/i) {
    setPackageFail($pkglist, $pkg, "Couldn't get depends: $@");
    return;
  }

  # @Xdeps is in disjunctive normal form.  That is, it is a list like:
  #	{{A v B v C} ^ {D v E} ^ {F}}
  # In other words, a list of dependencies, and each dependency is a
  # list of packages which can satisfy it.
  foreach my $depinfo ([\@bdeps, "build"], [\@rdeps, "run"]) {
    my($deps, $deptype) = @$depinfo;

    # If foo depends on bar, we start processing foo and
    # then recurse into bar.  What if bar then depends on foo?
    # If bar builddepends on foo, that's bad, don't try to
    # satisfy that alternative.  However, we do want to allow:
    #
    # foo: BuildDepends: bar-shlibs
    # bar: Has two splitoffs, bar-shlibs and bar, bar Depends: foo
    #
    # So, if a dep is PKGSTATUS_PROCESSING, that counts as resolved
    # if it's a non-build depend.
    my @status_ok = (PKGSTATUS_INSTALLED);
    push @status_ok, PKGSTATUS_PROCESSING if $deptype eq "run";

    my @status_failed = (PKGSTATUS_FAILED, PKGSTATUS_SKIP);

  DEP: foreach my $dep (@$deps) {
      my @alts = sort {
				# Prefer already-installed deps.

	my $status_a = $pkglist->{$a};
	my $score_a = 0;
	$score_a = 1 if defined($status_a) and grep {$status_a == $_} @status_ok;
	my $status_b = $pkglist->{$b};
	my $score_b = 0;
	$score_b = 1 if defined($status_b) and grep {$status_b == $_} @status_ok;

	$score_b <=> $score_a;
      } grep {$_ ne $pkg} FinkLib::filterSplitoffs(map {$_->get_name()} @$dep);

      next unless @alts;
      foreach my $alt (@alts) {
	my $depstat = $pkglist->{$alt};
	$depstat = PKGSTATUS_INSTALL unless defined($depstat);
	if (grep { $depstat == $_ } @status_failed or
	    ($deptype ne "run" and $depstat == PKGSTATUS_PROCESSING)) {
	  next;
	}

	$pkglist->{$alt} = PKGSTATUS_INSTALL if !defined($pkglist->{$alt});
	next DEP if grep {$pkglist->{$alt} == $_} @status_ok;
	recurseOnDepends($pkglist, $alt, 1, $finkfiles) and next DEP;
      }

      logPackageFail($pkg, "Can't figure out how to build.  Unsatisfied dependencies: " . join(" ", @alts));
      return;
    }
  }

  doLog("Building package $pkg...");
  my $srcdir = $Fink::Config::buildpath; # Suppress "used only once" warning
  $srcdir = "$Fink::Config::buildpath/" . $obj->get_fullname();

  my $buildcmd = "printf '\n\n' | fink --no-use-binary-dist --yes $FinkBuildFlags ";
  $buildcmd .= "--build-as-nobody " if $BuildNobody;
  if ($orig_status == PKGSTATUS_REBUILD) {
    $buildcmd .= "rebuild ";
  } else {
    $buildcmd .= "install ";
  }
  $buildcmd .= "$pkg 2>&1";
  my $ret = doBuild($buildcmd, $pkg);

  if ($ret != 0 and defined($BuildNobody) and $BuildNobody eq "try") {
    $buildcmd =~ s/ --build-as-nobody//;
    move("$RunDir/logs/$pkg.log", "$RunDir/logs/$pkg.log.nobody");
    doLog("Build of $pkg failed, trying as root...");
    $ret = doBuild($buildcmd, $pkg);
    if ($ret != 0) {
      unlink("$RunDir/logs/$pkg.log.nobody");
    } else {
      move("$RunDir/logs/$pkg.log.nobody", "$RunDir/nobody/$pkg.log");
    }
  }

  if ($ret != 0) {
    doLog("Build of $pkg failed!");
    my @failpkgs = $pkg;

    # Also, any splitoffs of this package have failed.
    my @relatives = FinkLib::getRelatives($obj);
    foreach (@relatives) {
      my $name = $_->get_name();
      push @failpkgs, $pkg;

      system("mv", $srcdir, "$RunDir/src/$pkg") or doLog("Couldn't move $srcdir to $RunDir/src/$pkg: $!");
    }

    $pkglist->{$_} = PKGSTATUS_FAILED foreach @failpkgs;
    updateCheckpoint(map { $_ => PKGSTATUS_FAILED } @failpkgs);
    return;
  } else {
    doLog("Build of $pkg succeeded!");
    system("rm", "-rf", $srcdir);

    my $src = $obj->get_debfile();
    my $deb = $obj->get_debname();
    if ($orig_status == PKGSTATUS_REBUILD) {
      getDebFiles($obj);
      getDebFiles($_) foreach FinkLib::getRelatives($obj);
    }

    my $dst = "$RunDir/pkginfo/binary-darwin-x86_64/$deb";
    if ($src ne $dst) {
      move($src, $dst);
      unlink("$FinkDir/fink/debs/$deb");
      symlink("$RunDir/pkginfo/binary-darwin-x86_64/$deb", "$FinkDir/fink/debs/$deb");
    }

    my @okpkgs = $pkg;
    foreach my $relative (FinkLib::getRelatives($obj)) {
      push @okpkgs, $relative->get_name();

      my $deb = $relative->get_debname();
      my $src = readlink("$FinkDir/fink/debs/$deb");
      my $dst = "$RunDir/pkginfo/binary-darwin-x86_64/$deb";
      if ($src ne $dst) {
	move($src, $dst);
	unlink("$FinkDir/fink/debs/$deb");
	symlink("$RunDir/pkginfo/binary-darwin-x86_64/$deb", "$FinkDir/fink/debs/$deb");
      }
    }

    $pkglist->{$_} = PKGSTATUS_INSTALLED foreach @okpkgs;
    updateCheckpoint(map { $_ => PKGSTATUS_INSTALLED } @okpkgs);
  }

  FinkLib::purgeNonEssential() unless $Dirty;

  if ($CheckFiles) {
    my @killqueue;

    find({no_chdir => 1, wanted => sub {
	    if (/\.deb$/ or $_ =~ /fink\.build$/  or $File::Find::name eq "$FinkDir/var/lib/fink/finkinfodb") {
	      $File::Find::prune = 1;
	    } elsif (!$finkfiles->{$File::Find::name}) {
	      doValidateWarn($pkg, "Leftover file $File::Find::name");
	      push @killqueue, $File::Find::name;
	    }
	  }}, $FinkDir);

    #system("rm", "-rf", @killqueue);
    $finkfiles->{$_} = 1 foreach @killqueue;
  }

  return 1;
}

# Try to build packages, adding to pkglist as we encounter deps.
sub buildAll {
  my($pkglist) = @_;

  my $finkfiles = {};
  if ($CheckFiles) {
    Fink::Config::set_options({"Pedantic" => 1});

    # One of the validation steps is to identify files left in /sw
    # by the build process.
    find({no_chdir => 1, wanted => sub {
	    $finkfiles->{$File::Find::name} = 1;
	  }}, $FinkDir);
  }

  my @newfails;
 PACKAGE: while(1) {
    my($pkg, $pkgval);
    foreach my $p (keys %$pkglist) {
      my $v = $pkglist->{$p};
      next unless $v == PKGSTATUS_REBUILD or $v == PKGSTATUS_INSTALL;
      $pkg = $p;
      $pkgval = $v;
      last;
    }

    if (!$pkg) {
      my @unsats = sort grep { $pkglist->{$_} == PKGSTATUS_PROCESSING } keys %$pkglist;
      if (@unsats) {
	doLog("Couldn't figure out how to build: " . join(", ", @unsats));
	return;
      } else {
	return 1;
      }
    }

    recurseOnDepends($pkglist, $pkg, 0, $finkfiles);
  }
}


### Checkpoint handling

sub restoreCheckpoint {
  my($checkpoint) = shift;
  my($pkglist);

  # We use eval "STRING" so that the variables in the checkpoint are
  # bound to this sub's lexical scope.

  open(CHECKPOINT, $checkpoint) or die "Couldn't open checkpoint: $!\n";
  my $cpdata = join("", <CHECKPOINT>);
  close CHECKPOINT;
  my $ret = eval "$cpdata";
  die "$@\n" if $@;
  die "Checkpoint didn't return true value .\n" unless $ret;

  prepSystem();
  injectPackages() unless $BuildAll;
  FinkLib::removeBuildLocks();

  doLog("Restored from checkpoint");
  doLog("Building packages");
  buildAll($pkglist);
  doLog("Done building");
  restoreSystem();
}

sub initCheckpoint {
  my($pkglist) = @_;

  open(CHECKPOINT, ">", "$RunDir/checkpoint");

  print CHECKPOINT Data::Dumper->Dump(
				      [$FinkDir, $RunDir, $BuildNobody, $BuildAll, $CheckFiles, $DoValidate, $pkglist],
				      [qw(FinkDir RunDir BuildNobody BuildAll CheckFiles DoValidate pkglist)]
				     );

  close CHECKPOINT;
}

# Updates the checkpoint after a package build.
sub updateCheckpoint {
  my(%changes) = @_;

  open(CHECKPOINT, ">>", "$RunDir/checkpoint");
  print CHECKPOINT "\$pkglist->{'$_'} = $changes{$_}; " foreach keys %changes;
  print CHECKPOINT "\n";
  close CHECKPOINT;
}
